Object-oriented attribute grammars have been introduced by several authors (e. g.
\*([[Gro90a\*(],Hed89\*(]])
as a promising notation for attribute grammars.
An overview of the current state of the art in this area is given in
\*([[Kos91\*(]].
The benefits are comparable to those of object-oriented programming languages.
It is a concise notation and flexible notation for language specifications.
The reuse of existing definitions is supported by the
possibility to specify new definitions as extensions or specializations of existing ones.
The duplication of information is avoided because common parts can be "factored out".
.pp
While the main building blocks of object-oriented programming languages are classes, the
nonterminals play this part in object-oriented attribute grammars. More precisely, the
notions nonterminal and production rule are unified. This means that there is exactly one
production rule for every nonterminal. Additionally, a relation between nonterminals is
specified, for example using chain rules, which describes a subtype relation or class
hierarchy among the nonterminals. This subtype relation serves for two purposes. First, it
allows to derive several different strings from one nonterminal because a nonterminal may
be replaced by a right-hand side corresponding to a nonterminal that is a subtype of the
replaced one. Second, the subtype relation describes the path for inheritance among the
nonterminals. The items that are subject to inheritance are right-hand side elements,
attributes, and attribute computations.
Inherited attribute computations may be overwritten in the subtype
by giving different computations for the same attributes.
.pp
Before we proceed we have to clarify the terminology:
Originally, context-free grammars as well as attribute grammars are derivation systems for
strings. In this paper we are interested in the specification of semantic analysis which is
based on an abstract syntax tree. Therefore we use grammars to describe the structure of
trees instead of strings.
.lp
In order to avoid confusion between the terms class, nonterminal, terminal, and (sub)type
we will use the term
.i "node type"
to cover all those meanings. The term node type is motivated through a realistic
description of what is happening: The node types specify the structure of the nodes of the
abstract syntax tree.
.lp
The attributes in attribute grammars are usually classified as
.i synthesized
and
.i inherited .
Following Hedin\*([<\*([[Hed89\*(]]\*(>] we use the term
.i "ancestral attribute"
instead of the standard
.i "inherited attribute"
since we use the term
.i inherited
in the object-oriented sense.
.pp
There is one problem that arises especially from the combination of ancestral attributes
and inheritance. Let A, B, and C be node types and let B be a subtype of A (B \(ib A)
having one ancestral attribute x. If the right-hand side of C contains an A, we have to
know whether to compute the attribute A.x or not. The static type is A, but the dynamic type
can be any subtype, that is A or B. If it is B we have to compute A.x, if it is A we may
not compute it.
The notions node type, subtype, and right-hand side are defined in section 2.
.pp
There are several solutions to this problem. First, one can restrict the definition of
ancestral attributes to top level node types, only. This makes the reuse of existing
node types very hard in particular in combination with multiple inheritance.
.pp
Second, one could use a dynamic dispatch technique which inspects the dynamic type of the
right-hand side child and decides during runtime whether to compute A.x or not. This
solution is rather inefficient because of its runtime overhead.
.pp
Most existing systems therefore allow single inheritance, only, with the additional
restriction that ancestral attributes have to be defined at top level node types. The
last restriction is not severe because it somehow coincides in a natural way with the
style of usual attribute grammars.
Hedin\*([<\*([[Hed89\*(]]\*(>] follows this argumentation and calls
object-oriented attribute grammars having the above problem not
.i "well formed" .
.pp
This paper introduces a third solution to the above mentioned problem. It allows for a
restricted form of multiple inheritance and still retains the capability to decide at
generation time which ancestral attributes have to be computed. Attribute evaluators
can still be implemented efficiently as dynamic dispatch is avoided.
.pp
In section 2 we formally define object-oriented attribute grammars with single inheritance.
Section 3 contains two simple examples using single inheritance.
Section 4 extends the definition of object-oriented attribute grammars to multiple
inheritance.
Section 5 presents an elaborate example with multiple inheritance.
In section 6 we compare our approach with pure attribute grammars and with object-oriented
programming in order to reveal the common properties as well as the differences.
Section 7 summarizes the results.
.sh 1 "Single Inheritance"
.lp
This section formally defines the principles of object-oriented attribute grammars with
single inheritance.
As starting point we shortly recall the traditional definition of attribute grammars
\*([[Knu68\*(],Knu71\*(]].
.pp
An attribute grammar is an extension of a context-free grammar.
A context-free grammar is denoted by G = (N, T, P, Z) where
N is the set of nonterminals,
T is the set of terminals,
P is the set of productions, and
Z \(mo N is the
.i start
symbol, which cannot appear on the right-hand side of any production in P.
The set V = N \(cu T is called the vocabulary.
Each production p \(mo P has the form $ p:~X~\(->~alpha $ where X \(mo N and
$ alpha~\(mo~V sup "*" $.
The relation \(:> (directly derives) is defined over strings in $ V sup "*" $ as follows:
if $ p:~X~\(->~alpha $, p \(mo P, $ nu X omega~\(mo~V sup "*" $,
$ nu alpha omega~\(mo~V sup "*" $ then
$ nu X omega~\(:>~nu alpha omega $.
The relation $ \(:> sup "*" $ is the transitive and reflexive closure of \(:>.
The language L(G) is defined as $ L(G)~=~"{"~w~|~Z~\(:> sup *~w~"}" $.
.pp
An attribute grammar augments a context-free grammar by attributes and attribute
computations. A set of attributes is associated with each symbol in V.
Attribute computations are added to every production describing how to compute attribute
values in the local context of a production.
This simple view of attribute grammars shall suffice for the scope of this paper.
.pp
In general there can be several productions having the same nonterminal on the left-hand side.
This allows for different derivations starting from one nonterminal. In object-oriented
attribute grammars, one production is permitted for one left-hand side symbol, only.
This way the notions production and nonterminal (vocabulary respectively) are unified
and are termed
.i "node type"
as already mentioned. Several different derivations are made possible through the
newly introduced subtype relation.
.pp
An object-oriented attribute grammar is formally denoted by G = (N, T, A, C, Z) where
N is the set of nonterminals,
T is the set of terminals,
A is the set of attributes,
C is the set of attribute computations, and
Z is the start symbol (Z \(mo N).
The set NT = N \(cu T is called the set of
.i "node types" .
Each element n \(mo NT is associated with a tuple n: (R, B, D, S) where
$ R~\(mo~NT sup "*" $ is the right-hand side,
$ B~\(mo~A sup "*" $ is the set of attributes,
$ D~\(mo~C sup "*" $ is the set of attribute computations, and
S \(mo NT is the base type.
.pp
The elements of NT induce a relation \(ib (subtype) over NT as follows:
if $ n:~( alpha ,~beta ,~delta ,~m )~\(mo~NT $ then n \(ib m.
m is called
.i base
or
.i super
type, n is called
.i derived
type or
.i subtype .
The relation \(ib is transitive: if n \(ib m and m \(ib o then n \(ib o.
.pp
The relation \(:> (directly derives) is defined here only for the context-free or syntactic
part of an object-oriented attribute grammar. There are two possibilities for derivations
which are defined over strings in $ NT sup "*" $ as follows:
.lp
.nf
.ta 3.9c
if $ nu n sub i omega~\(mo~NT sup "*" $ and $ n sub 1 :~( alpha sub 1 ,~beta sub 1 ,~delta sub 1 ,~n sub 0 )~\(mo~NT, $
$ n sub 2 :~( alpha sub 2 ,~beta sub 2 ,~delta sub 2 ,~n sub 1 )~\(mo~NT, $
$ ... $
$ n sub i :~( alpha sub i ,~beta sub i ,~delta sub i ,~n sub i-1 )~\(mo~NT $ then $ nu n sub i omega~\(:>~nu alpha sub 1 alpha sub 2 ... alpha sub i omega $.
.lp
.nf
if $ nu n omega~\(mo~NT sup "*" $ and $ m~\(ib~n $ then $ nu n omega~\(:>~nu m omega $.
.lp
We assume the existence of a predefined node type $ n sub 0 :~(\(o/,~\(o/,~\(o/,~-) $ with
empty components. In a direct derivation step, a node type can be replaced by its right-hand
side $ ( alpha sub 1 ... alpha sub i ) $ or by one of its subtypes (m). All replacing
right-hand sides are the union of right-hand sides according to the subtype hierarchy.
The relation $ \(:> sup "*" $ is the transitive and reflexive closure of \(:>.
The language L(G) is defined as $ L(G)~=~"{"~w~|~Z~\(:> sup "*"~w~"}" $.
.pp
The subtype relation has the following properties: a derived node type inherits the
right-hand side, the attributes, and the attribute computations from its base type. As
consequence of the transitive nature of this relation, a derived type inherits all the
components from all base types according to the subtype hierarchy.
It may extend the set of inherited items by defining
additional right-hand side elements, attributes, or attribute computations. All accumulated
right-hand side elements and attributes must be distinct because they are
united. An attribute computation for an attribute may overwrite an inherited one.
.\" The definition of the subtype relation allows exactly single inheritance.
.sh 1 Example
.lp
We implemented an attribute grammar system called
.i ag
based on object-oriented attribute grammars which is part of the Karlsruhe Toolbox for
Compiler Construction\*([<\*([[GrE90\*(]]\*(>].
It supports the kinds of single and multiple inheritance described in this paper.
The following examples of object-oriented attribute grammars with single inheritance
are written in the specification language of
.i ag .
The language tries to adhere to the conventional style of context-free grammars
as far as possible. It offers far more features for practical usage than can be
explained here. The interested reader is referred to the user's manual\*([<\*([[Gro89\*(]]\*(>].
.pp
An attribute grammar is given in the form of nested node type definitions. The nesting
expresses the subtype hierarchy or the subtype relation. A node type definition consists of
properties of the node type followed by a list of subtype definitions enclosed in angle
brackets < >. The properties include the structural or syntactic definition (right-hand
side), attribute definitions, and attribute computations.
